/**
 * 最小覆盖子串
 *
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 *
 * 示例 2：
 * 输入：s = "a", t = "a"
 * 输出："a"
 * 解释：整个字符串 s 是最小覆盖子串。
 *
 * 示例 3:
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 *
 * 提示：
 * m == s.length
 * n == t.length
 * 1 <= m, n <= 105
 * s 和 t 由英文字母组成
 *
 *
 * 进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
 */


/**
 * 我们用 两个 hash表 来记录, 首先, 我们先用一个 hash2 记录 t 中所有的
 * 字符, 然后在遍历 s, 用另一个 hash1 记录, 要是 满足需求, 就将这个字符
 * 加入 hash1, 再用一个 用来标记是否满足最终需求, 要是满足了, 再比较要求
 * 的最短长度, 要是更短, 就更新最短值
 * 时间复杂度 : O(m + n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public String minWindow(String s, String t) {

        // 字符转数组
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();

        int n = ch1.length;

        // 用来记录最短的长度和开始位置
        int begin = -1;
        int minLen = n + 1;

        // 一共要记录的字符数
        int kinds = ch2.length;

        // 两个 hash 表, 我们直接用 int 型数组来记录, 这样可以节省空间
        int[] hash1 = new int[126];
        int[] hash2 = new int[126];

        // 先将 目标 字符 一个一个加入 hash2
        for (char x : ch2) {
            hash2[x]++;
        }

        // 遍历 ch1, 我们要记录一个区间, 所以用 left right 圈区间
        for (int left = 0, right = 0, k = 0; right < n; right++) {

            // 入字符
            char in = ch1[right];

            // 判断是否是否满足需求一
            if (++hash1[in] <= hash2[in]) {

                k++;

            }

            // 要是满足需求就要比较长度 和 出字符
            while (k == kinds) {

                // 比较长度
                if (minLen > right -left + 1) {

                    begin = left;
                    minLen = right - left + 1;

                }

                // 出字符
                if (left <= right) {

                    // 出字符
                    char out = ch1[left++];

                    if (hash1[out]-- <= hash2[out]) {

                        k--;

                    }
                }
            }

        }

        // 返回结果
        return begin == -1 ? "" : s.substring(begin, begin + minLen);
    }
}